// 二叉树的右视图
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size())
        {
            res.push_back(q.front()->val);
            int sz = q.size();
            while (sz--)
            {
                TreeNode* node = q.front();
                q.pop();
                if (node->right) q.push(node->right);
                if (node->left) q.push(node->left);
            }
        }
        return res;
    }
};

// 二叉树展开为链表
class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> vt;
        dfs(root, vt);
        for (int i = 1; i < vt.size(); i++)
        {
            TreeNode* prev = vt[i - 1], *cur = vt[i];
            prev->left = nullptr;
            prev->right = cur;
        }
    }
    void dfs(TreeNode* root, vector<TreeNode*>& vt)
    {
        if (root)
        {
            vt.push_back(root);
            dfs(root->left, vt);
            dfs(root->right, vt);
        }
    }
};

// 从前序与中序遍历序列构造二叉树
class Solution {
    unordered_map<int, int> index;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); i++)
        {
            index[inorder[i]] = i;
        }
        return dfs(preorder, 0, 0, inorder.size() - 1);
    }
    TreeNode* dfs(vector<int>& preorder, int root, int l, int r)
    {
        if (l > r) return nullptr;
        TreeNode* node = new TreeNode(preorder[root]);
        int id = index[preorder[root]];
        node->left = dfs(preorder, root + 1, l, id - 1);
        node->right = dfs(preorder, root + id - l + 1, id + 1, r);
        return node;
    }
};
